{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Pseudo-Palindromic Paths in a Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pseudoPalindromicPaths "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树中的伪回文路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「<strong>伪回文</strong>」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。</p>\n",
    "\n",
    "<p>请你返回从根到叶子节点的所有路径中&nbsp;<strong>伪回文&nbsp;</strong>路径的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/23/palindromic_paths_1.png\" style=\"height: 201px; width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,3,1,3,1,null,1]\n",
    "<strong>输出：</strong>2 \n",
    "<strong>解释：</strong>上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 [2,3,3] ，绿色路径 [2,1,1] 和路径 [2,3,1] 。\n",
    "     在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ，绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/23/palindromic_paths_2.png\" style=\"height: 314px; width: 300px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,1,1,1,3,null,null,null,null,null,1]\n",
    "<strong>输出：</strong>1 \n",
    "<strong>解释：</strong>上图为给定二叉树。总共有 3 条从根到叶子的路径：绿色路径 [2,1,1] ，路径 [2,1,3,1] 和路径 [2,1] 。\n",
    "     这些路径中只有绿色路径是伪回文路径，因为 [2,1,1] 存在回文排列 [1,2,1] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [9]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>给定二叉树的节点数目在范围&nbsp;<code>[1, 10<sup>5</sup>]</code> 内</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [pseudo-palindromic-paths-in-a-binary-tree](https://leetcode.cn/problems/pseudo-palindromic-paths-in-a-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [pseudo-palindromic-paths-in-a-binary-tree](https://leetcode.cn/problems/pseudo-palindromic-paths-in-a-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,1,3,1,null,1]', '[2,1,1,1,3,null,null,null,null,null,1]', '[9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        t=[]\n",
    "        d={}\n",
    "        d[root.val]=1\n",
    "        h=root\n",
    "        k=0\n",
    "        n=0\n",
    "        flag=False\n",
    "        if root.left==None and root.right==None:\n",
    "            return 1\n",
    "        while True:\n",
    "            if h.left!=None or h.right!=None:          \n",
    "                if h.left!=None: \n",
    "                    t.append([h,0])           \n",
    "                    h=h.left\n",
    "                else:\n",
    "                    t.append([h,1])\n",
    "                    h=h.right                \n",
    "                if h.val in d.keys():\n",
    "                    d[h.val]+=1\n",
    "                else:\n",
    "                    d[h.val]=1\n",
    "                flag=True\n",
    "            else: \n",
    "                if len(t)==0:\n",
    "                    break\n",
    "                if flag==True:\n",
    "                    a=0\n",
    "                    for i in d.values():\n",
    "                        if i%2==1:\n",
    "                            a+=1\n",
    "                            if a>1:\n",
    "                                break\n",
    "                    if a<=1:\n",
    "                        n+=1\n",
    "                d[h.val]-=1\n",
    "                m=t.pop()\n",
    "                h=m[0]\n",
    "                k=m[1]\n",
    "                if k==0:\n",
    "                    h.left=None\n",
    "                else:\n",
    "                    h.right=None\n",
    "                flag=False\n",
    "        return n\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        self.res=[]\n",
    "        def dfs(root,path):\n",
    "            if not root:\n",
    "                return ''\n",
    "\n",
    "            if ((not root.left) and (not root.right)):\n",
    "                self.res.append(path+str(root.val))\n",
    "            if root.left:\n",
    "                dfs(root.left,path+str(root.val))\n",
    "            if root.right:\n",
    "                dfs(root.right,path+str(root.val))\n",
    "        dfs(root,'')\n",
    "        \n",
    "        print(self.res)\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        def panduan(lis):\n",
    "            a=collections.Counter(lis)\n",
    "            b=[]\n",
    "            for i,j in a.items():\n",
    "                b.append(j)\n",
    "            b=sorted(b)\n",
    "            key=0\n",
    "            for i in range(len(b)):\n",
    "                if b[i]%2==1:\n",
    "                    key+=1\n",
    "            if key>1:\n",
    "                return False\n",
    "            return True              \n",
    "        key=0       \n",
    "        for i in self.res:\n",
    "            if panduan(i):\n",
    "                key+=1\n",
    "        return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(root, dic):\n",
    "            if not root: return \n",
    "            dic_copy = dic.copy()\n",
    "            dic_copy[root.val] +=1\n",
    "            if not root.left and not root.right:\n",
    "                if sum(cnt%2 == 1 for cnt in dic_copy.values()) <= 1:\n",
    "                    self.res +=1\n",
    "                    return\n",
    "            if root.left:\n",
    "                dfs(root.left, dic_copy)\n",
    "            if root.right:\n",
    "                dfs(root.right, dic_copy)\n",
    "        dfs(root, collections.defaultdict(int))\n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        def helper(root, path):\n",
    "            if not root:\n",
    "                return\n",
    "            path ^= (1 << root.val)\n",
    "            if not root.left and not root.right:\n",
    "                if path == 0 or path&(path-1) == 0:\n",
    "                    self.res += 1\n",
    "                return\n",
    "            helper(root.left, path)\n",
    "            helper(root.right, path)\n",
    "\n",
    "        self.res = 0\n",
    "        helper(root, 0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "\n",
    "        def dfs(root, dic) -> int:\n",
    "            if root == None:\n",
    "                return 0\n",
    "            dic[root.val] += 1          #回溯算法，添加root\n",
    "            if root.left == root.right == None:             #如果为叶结点\n",
    "                if sum(cnt%2==1 for cnt in dic.values()) <= 1:\n",
    "                    dic[root.val] -= 1          #回溯！！！！！\n",
    "                    return 1\n",
    "                else:\n",
    "                    dic[root.val] -= 1          #回溯！！！！！\n",
    "                    return 0\n",
    "            res = 0\n",
    "            if root.left:\n",
    "                res += dfs(root.left, dic)\n",
    "            if root.right:\n",
    "                res += dfs(root.right, dic)\n",
    "            dic[root.val] -= 1                  #回溯！！！！！！！！！\n",
    "            return res\n",
    "\n",
    "        dic = collections.defaultdict(int)\n",
    "        return dfs(root, dic)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        if not root: return 0\n",
    "        level = [(root, 1<<root.val)]\n",
    "        result = 0\n",
    "        while level:\n",
    "            newlevel = []\n",
    "            for node, mask in level:\n",
    "                if not node.left and not node.right:\n",
    "                    if bin(mask).count('1')<=1:\n",
    "                        result += 1\n",
    "                    continue\n",
    "                if node.left:\n",
    "                    newlevel.append((node.left, mask ^ (1<<node.left.val)))\n",
    "                if node.right:\n",
    "                    newlevel.append((node.right, mask ^ (1<<node.right.val)))\n",
    "            level = newlevel\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        node_list = [root]\n",
    "        initial_count = [0,0,0,0,0,0,0,0,0]\n",
    "        initial_count[root.val - 1] = 1\n",
    "        count = [initial_count]\n",
    "        pointer = 0\n",
    "        ans = 0\n",
    "\n",
    "        def check(x):\n",
    "            odd_count = 0\n",
    "            for i in x:\n",
    "                if i % 2 == 1:\n",
    "                    odd_count += 1\n",
    "            if odd_count > 1:\n",
    "                return 0\n",
    "            return 1\n",
    "\n",
    "        while pointer < len(node_list):\n",
    "            node = node_list[pointer]\n",
    "            count_now = count[pointer]\n",
    "            if node.left is None and node.right is None:\n",
    "                ans += check(count_now)\n",
    "            if node.left is not None:\n",
    "                node_list.append(node.left)\n",
    "                new_count = []\n",
    "                for i in range(0, 9):\n",
    "                    new_count.append(count_now[i])\n",
    "                new_count[node.left.val - 1] += 1\n",
    "                count.append(new_count)\n",
    "            if node.right is not None:\n",
    "                node_list.append(node.right)\n",
    "                new_count = []\n",
    "                for i in range(0, 9):\n",
    "                    new_count.append(count_now[i])\n",
    "                new_count[node.right.val - 1] += 1\n",
    "                count.append(new_count)\n",
    "            pointer += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        queue = collections.deque()\n",
    "        state = ans = 0\n",
    "        state ^= 1 << root.val\n",
    "        queue.append((root, state))\n",
    "\n",
    "        while queue:\n",
    "            node, state = queue.popleft()\n",
    "            \n",
    "            if node.left:\n",
    "                state ^= 1 << node.left.val\n",
    "                queue.append((node.left, state))\n",
    "                state ^= 1 << node.left.val # 还有这么一步。将每个位置的状态用state来表示...，这也太绝了趴\n",
    "            if node.right:\n",
    "                state ^= 1 << node.right.val\n",
    "                queue.append((node.right, state))\n",
    "                state ^= 1 << node.right.val\n",
    "            if not node.left and not node.right and bin(state).count('1') <= 1:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        st, node = [], root\n",
    "        ans, path = 0, 0\n",
    "\n",
    "        while st or node:\n",
    "            while node:\n",
    "                path ^= 1 << node.val\n",
    "                if not node.left and not node.right:\n",
    "                    ans += path & (path - 1) == 0\n",
    "                st.append([node, path])\n",
    "                node = node.left\n",
    "            node, path = st.pop()\n",
    "            node = node.right\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        def check(track):\n",
    "            return len([v for v in track.values() if v % 2]) <= 1\n",
    "        \n",
    "        def bfs(root):\n",
    "            res = 0\n",
    "            queue = deque([(root, Counter())])\n",
    "            while queue:\n",
    "                for _ in range(len(queue)):\n",
    "                    cur, track = queue.popleft()\n",
    "                    if cur.left is None and cur.right is None and check(track + Counter({cur.val : 1})):\n",
    "                        res += 1\n",
    "\n",
    "                    if cur.left is not None:\n",
    "                        queue.append((cur.left, track + Counter({cur.val : 1})))\n",
    "                    if cur.right is not None:\n",
    "                        queue.append((cur.right, track + Counter({cur.val : 1})))\n",
    "            return res\n",
    "        \n",
    "        return bfs(root)\n",
    "\n",
    "    def pseudoPalindromicPaths(self, root: TreeNode) -> int:\n",
    "        def check(path):\n",
    "            return bin(path).count('1') <= 1\n",
    "        \n",
    "        def bfs(root):\n",
    "            res = 0\n",
    "            path = 0\n",
    "            path ^= (1 << root.val)\n",
    "            queue = [(root, path)]\n",
    "            while queue:\n",
    "                for _ in range(len(queue)):\n",
    "                    cur, path = queue.pop(0)\n",
    "                    if cur.left is None and cur.right is None and check(path):\n",
    "                        res += 1\n",
    "                    if cur.left is not None:\n",
    "                        queue.append((cur.left, path ^ (1 << cur.left.val)))\n",
    "                    if cur.right is not None:\n",
    "                        queue.append((cur.right, path ^ (1 << cur.right.val)))\n",
    "            return res\n",
    "        \n",
    "        return bfs(root)\n",
    "\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        def check(path):\n",
    "            dic = collections.defaultdict(int)\n",
    "            for n in path:\n",
    "                dic[n] += 1\n",
    "                \n",
    "            return len([v for v in dic.values() if v % 2]) <= 1\n",
    "        \n",
    "        def bfs(root):\n",
    "            res = 0\n",
    "            queue = deque([(root, [])])\n",
    "            while queue:\n",
    "                for _ in range(len(queue)):\n",
    "                    cur, path = queue.popleft()\n",
    "                    if cur.left is None and cur.right is None and check(path + [cur.val]):\n",
    "                        res += 1\n",
    "                    if cur.left is not None:\n",
    "                        queue.append((cur.left, path + [cur.val]))\n",
    "                    if cur.right is not None:\n",
    "                        queue.append((cur.right, path + [cur.val]))\n",
    "            return res\n",
    "        \n",
    "        return bfs(root)\n",
    "\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        def check(path):\n",
    "            return bin(path).count('1') <= 1\n",
    "        \n",
    "        def bfs(root):\n",
    "            res = 0\n",
    "            path = 0\n",
    "            path ^= (1 << root.val)\n",
    "            queue = [(root, path)]\n",
    "            while queue:\n",
    "                for _ in range(len(queue)):\n",
    "                    cur, path = queue.pop(0)\n",
    "                    if cur.left is None and cur.right is None and check(path):\n",
    "                        res += 1\n",
    "                    if cur.left is not None:\n",
    "                        path ^= (1 << cur.left.val)\n",
    "                        queue.append((cur.left, path))\n",
    "                        path ^= (1 << cur.left.val) # 回退\n",
    "                    if cur.right is not None:\n",
    "                        path ^= (1 << cur.right.val)\n",
    "                        queue.append((cur.right, path))\n",
    "                        path ^= (1 << cur.right.val) # 回退\n",
    "            return res\n",
    "        \n",
    "        return bfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        res, stack = 0, [(root, 0)]\n",
    "        while stack:\n",
    "            u, w = stack.pop()\n",
    "            w ^= 1<<u.val\n",
    "            res += not u.left and not u.right and w.bit_count()<=1\n",
    "            stack.extend((chi,w) for chi in [u.right,u.left] if chi)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        flag = 0x00\n",
    "        # 0 ^ 1 ^ 1 ... ^ 1 出现奇数次为1 偶数次为0\n",
    "        # palindromic判断 至多只有一个数出现次数为奇数 flag == 0 or flag&(-flag) == flag\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        while root or len(stack) != 0:\n",
    "            while root:\n",
    "                flag ^= 1 << root.val\n",
    "                if root.left is None and root.right is None:\n",
    "                    if flag &(-flag) == flag:\n",
    "                        ans += 1\n",
    "                stack.append((root.right, flag))\n",
    "                root = root.left\n",
    "            # leaf node\n",
    "            root, flag = stack.pop() \n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        count = 0\n",
    "        stack = [(root, 0)]\n",
    "\n",
    "        while stack:\n",
    "            node, path = stack.pop()\n",
    "\n",
    "            if node:\n",
    "                path ^= (1 << node.val)\n",
    "\n",
    "                if not node.left and not node.right:\n",
    "                    if path & (path - 1) == 0:\n",
    "                        count += 1\n",
    "                else:\n",
    "                    stack.append((node.right, path))\n",
    "                    stack.append((node.left, path))\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        count = 0\n",
    "        stack = [(root, 0)]\n",
    "\n",
    "        while stack:\n",
    "            node, path = stack.pop()\n",
    "\n",
    "            if node:\n",
    "                path ^= (1 << node.val)\n",
    "\n",
    "                if not node.left and not node.right:\n",
    "                    if path & (path - 1) == 0:\n",
    "                        count += 1\n",
    "                else:\n",
    "                    stack.append((node.right, path))\n",
    "                    stack.append((node.left, path))\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        TreeNode.__repr__ = lambda x: str(x.val)\n",
    "        queue = [root]\n",
    "        counter = 0\n",
    "        path_values = set()\n",
    "        visited = set()\n",
    "\n",
    "        while queue:\n",
    "            node = queue[-1]\n",
    "            if node.val in path_values:\n",
    "                path_values.remove(node.val)\n",
    "            else:\n",
    "                path_values.add(node.val)\n",
    "            \n",
    "            for child in (node.right, node.left):\n",
    "                if child is not None and child not in visited:\n",
    "                    queue.append(child)\n",
    "\n",
    "            if node == queue[-1]:\n",
    "                if node not in visited:\n",
    "                    if len(path_values) < 2:\n",
    "                        counter += 1\n",
    "\n",
    "                    if node.val in path_values:\n",
    "                        path_values.remove(node.val)\n",
    "                    else:\n",
    "                        path_values.add(node.val)\n",
    "                queue.pop()\n",
    "            visited.add(node)\n",
    "        \n",
    "        return counter\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        # def F(r, d):\n",
    "        #     if not r:\n",
    "        #         return 0\n",
    "        #     d ^= 1 << (r.val - 1)\n",
    "        #     if not r.left and not r.right:\n",
    "        #         return not d & (d - 1)\n",
    "        #     return F(r.left, d) + F(r.right, d)\n",
    "        # return int(F(root, 0))\n",
    "        ans = [0]\n",
    "\n",
    "        def loop(r):\n",
    "            if not r.left and not r.right:\n",
    "                if sum(r.val) < 2:\n",
    "                    ans[0] += 1\n",
    "                return\n",
    "            if r.left:\n",
    "                temp = r.val[:]\n",
    "                temp[r.left.val] = 0 if temp[r.left.val] else 1\n",
    "                r.left.val = temp\n",
    "                loop(r.left)\n",
    "            \n",
    "            if r.right:\n",
    "                temp = r.val[:]\n",
    "                temp[r.right.val] = 0 if temp[r.right.val] else 1\n",
    "                r.right.val = temp\n",
    "                loop(r.right)\n",
    "            \n",
    "        temp = root.val\n",
    "        root.val = [0] * 10\n",
    "        root.val[temp] = 1\n",
    "        loop(root)\n",
    "\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        import numpy as np\n",
    "        table=np.zeros((2,10),np.int8)\n",
    "        table[0,:]=1\n",
    "        def func(root,table):\n",
    "            table[1][root.val],table[0][root.val]=table[0][root.val],table[1][root.val]\n",
    "            if root.left is None and root.right is None:\n",
    "                if np.sum(table[1,:])<=1:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                rst=0\n",
    "                if root.left:\n",
    "                    rst+=func(root.left,table.copy())\n",
    "                if root.right:\n",
    "                    rst+=func(root.right,table.copy())\n",
    "                return rst\n",
    "        return func(root,table)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        root.path = [root.val]\n",
    "        nodeList = [root]\n",
    "        result = 0\n",
    "        while len(nodeList) > 0:\n",
    "            node = nodeList.pop(0)\n",
    "            if node.left != None:\n",
    "                path = node.path[:]\n",
    "                path.append(node.left.val)\n",
    "                node.left.path = self.tripPath(path)\n",
    "                nodeList.append(node.left)\n",
    "            if node.right != None:\n",
    "                path = node.path[:]\n",
    "                path.append(node.right.val)\n",
    "                node.right.path = self.tripPath(path)\n",
    "                nodeList.append(node.right)\n",
    "            if node.left == None and node.right == None:\n",
    "                if self.check(node.path):\n",
    "                    result += 1\n",
    "        return result\n",
    "\n",
    "    def tripPath(self, path):\n",
    "        if len(path) <= 1:\n",
    "            return path\n",
    "        \n",
    "        index = path.index(path[-1])\n",
    "        if index == len(path) - 1:\n",
    "            return path\n",
    "        else:\n",
    "            return path[:index] + path[index + 1: -1]\n",
    "\n",
    "    def check(self, path):\n",
    "        letterNum = {}\n",
    "        numbers = 0\n",
    "        for l in path:\n",
    "            if l in letterNum:\n",
    "                letterNum[l] += 1\n",
    "            else:\n",
    "                letterNum[l] = 1\n",
    "        for (key, value) in letterNum.items():\n",
    "            if value % 2 != 0:\n",
    "                numbers += 1\n",
    "        return numbers <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.values = []\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        closed = [root]\n",
    "        root.values = [root.val]\n",
    "        out = 0\n",
    "        while closed:\n",
    "            tmp = closed.pop(0)\n",
    "            # print(tmp.val, tmp.values)\n",
    "            if tmp.left:\n",
    "                closed.append(tmp.left)\n",
    "                if tmp.left.val in tmp.values:\n",
    "                    tmp.left.values = tmp.values[:]\n",
    "                    tmp.left.values.remove(tmp.left.val)\n",
    "                else:\n",
    "                    tmp.left.values = tmp.values[:]\n",
    "                    tmp.left.values.append(tmp.left.val)\n",
    "            # print(\"111:\",tmp.values)\n",
    "            if tmp.right:\n",
    "                closed.append(tmp.right)\n",
    "                if tmp.right.val in tmp.values:\n",
    "                    tmp.right.values = tmp.values[:]\n",
    "                    tmp.right.values.remove(tmp.right.val)\n",
    "                else:\n",
    "                    tmp.right.values = tmp.values[:]\n",
    "                    tmp.right.values.append(tmp.right.val)\n",
    "            if not tmp.left and not tmp.right and len(tmp.values)<=1:\n",
    "                out+=1\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self,root,temp):\n",
    "        n=temp^(1<<root.val)\n",
    "        if not root.left and not root.right:\n",
    "            if n==0 or (n&(n-1))==0:\n",
    "                self.ans+=1\n",
    "        if root.left:\n",
    "            self.dfs(root.left,n)\n",
    "        if root.right:\n",
    "            self.dfs(root.right,n)\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.ans=0\n",
    "        self.dfs(root,0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        nums = 0\n",
    "        self.dfs(root, nums)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, node, n):\n",
    "        tmp = n ^ (1 << node.val)\n",
    "        if not node.left and not node.right:\n",
    "            if not tmp or not (tmp & (tmp - 1)):\n",
    "                self.res += 1\n",
    "            return \n",
    "        if node.left:\n",
    "            self.dfs(node.left, tmp)\n",
    "        if node.right:\n",
    "            self.dfs(node.right, tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        d = [0] * 10\n",
    "        self.res = 0\n",
    "        self.search(root, d)\n",
    "        return self.res\n",
    "        \n",
    "    def search(self, root, d):\n",
    "        d[root.val] += 1\n",
    "        if root.left == None and root.right == None:\n",
    "            odd = 0\n",
    "            for v in d:\n",
    "                if v % 2 == 1:\n",
    "                    odd += 1\n",
    "            if odd <= 1:\n",
    "                self.res += 1\n",
    "        if root.left:\n",
    "            self.search(root.left, d)\n",
    "        if root.right:\n",
    "            self.search(root.right, d)\n",
    "        d[root.val] -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        l = [0,0,0,0,0,0,0,0,0,0]\n",
    "        if not root:\n",
    "            return 0\n",
    "        return self.depthTrival(root,l)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "    def getHuiWen(self,l):\n",
    "        flag = False\n",
    "        \n",
    "        for i in l:\n",
    "            if i & 1 == 1:\n",
    "                if flag:\n",
    "                    return 0\n",
    "                else:\n",
    "                    flag = True\n",
    "        return 1\n",
    "                \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "    def getDepth(self,root):\n",
    "        if root == None:\n",
    "            return 0\n",
    "        leftDepth = self.getDepth(root.left)\n",
    "        rightDepth = self.getDepth(root.rgiht)\n",
    "        return max(leftDepth,rightDepth)+1\n",
    "\n",
    "    def depthTrival(self,root,l):\n",
    "        l[root.val] += 1\n",
    "        if root.left == None and root.right == None:\n",
    "            print(l)\n",
    "            return self.getHuiWen(l)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        if root.left != None:\n",
    "            left = self.depthTrival(root.left,l)\n",
    "            l[root.left.val] -= 1\n",
    "        if root.right != None:\n",
    "            right = self.depthTrival(root.right,l)\n",
    "            l[root.right.val] -= 1\n",
    "        return right+left\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self, cou = 0):\n",
    "        self.cou = cou\n",
    "\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        li = []\n",
    "        self.patch(li, root)\n",
    "        return self.cou\n",
    "\n",
    "    def patch(self, ls, node):\n",
    "        if ls.count(node.val) == 0:\n",
    "            ls.append(node.val)\n",
    "        else:\n",
    "            ls.remove(node.val)\n",
    "        if not node.left and not node.right:\n",
    "            if len(ls) <= 1:\n",
    "                self.cou += 1\n",
    "            return\n",
    "        if node.left:\n",
    "            self.patch(ls.copy(), node.left)\n",
    "        if node.right:\n",
    "            self.patch(ls.copy(), node.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        count = 0\n",
    "        def dfs(node,record):\n",
    "            nonlocal count\n",
    "            if node.val in record:\n",
    "                del record[node.val]\n",
    "            else:\n",
    "                record[node.val] = True\n",
    "           \n",
    "            if node.left:\n",
    "                #print(record,end = 'a\\n')\n",
    "                dfs(node.left,record)\n",
    "                if node.left.val in record:\n",
    "                    del record[node.left.val]\n",
    "                else:\n",
    "                    record[node.left.val] = True\n",
    "              #  print(record,end = 'b\\n')\n",
    "            if node.right:\n",
    "                dfs(node.right,record)\n",
    "                if node.right.val in record:\n",
    "                    del record[node.right.val]\n",
    "                else:\n",
    "                    record[node.right.val] = True\n",
    "            if not node.left and not node.right:\n",
    "                if len(record) <2:\n",
    "                    count += 1\n",
    "        dfs(root,{})\n",
    "        return count\n",
    "\n",
    "                                                                                                                                                                                                                                                                                                                                                                      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: TreeNode) -> int:\n",
    "        result = 0\n",
    "        def helper(root, record):\n",
    "            if not root:\n",
    "                return\n",
    "            record ^= (1 << root.val)\n",
    "            if not root.left and not root.right:\n",
    "                if bin(record).count(\"1\") < 2:\n",
    "                    nonlocal result\n",
    "                    result += 1\n",
    "                return\n",
    "            helper(root.left, record)\n",
    "            helper(root.right, record)\n",
    "        helper(root, 0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node, b):\n",
    "            b ^= 1 << node.val\n",
    "            if not node.left and not node.right:\n",
    "                return 1 if (b == 0 or (b & (b - 1) == 0)) else 0\n",
    "            l = dfs(node.left, b) if node.left else 0\n",
    "            r = dfs(node.right, b) if node.right else 0\n",
    "            return l + r\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self,root):\n",
    "        if root.val not in self.pre_st:\n",
    "            self.pre_st.add(root.val)\n",
    "        else:\n",
    "            self.pre_st.remove(root.val)\n",
    "        if root.left is None and root.right is None:\n",
    "            print(root.val, self.pre_st)\n",
    "            if len(self.pre_st)<=1:\n",
    "                self.res += 1\n",
    "        else:\n",
    "            if root.left is not None:\n",
    "                self.dfs(root.left)\n",
    "            if root.right is not None:\n",
    "                self.dfs(root.right)\n",
    "        if root.val not in self.pre_st:\n",
    "            self.pre_st.add(root.val)\n",
    "        else:\n",
    "            self.pre_st.remove(root.val)\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        self.pre_st = set()\n",
    "        self.res = 0\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            self.dfs(root)\n",
    "            return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        self.li = set()\n",
    "        self.num = 0\n",
    "        def func(node):\n",
    "            if node.val in self.li:\n",
    "                self.li.remove(node.val)\n",
    "            else:\n",
    "                self.li.add(node.val)\n",
    "            if not node.left and not node.right:\n",
    "                print(node, self.li)\n",
    "                if len(self.li) <= 1:\n",
    "                    self.num += 1\n",
    "                if node.val in self.li:\n",
    "                    self.li.remove(node.val)\n",
    "                else:\n",
    "                    self.li.add(node.val)\n",
    "                return\n",
    "            if node.left:\n",
    "                func(node.left)\n",
    "            if node.right:\n",
    "                func(node.right)\n",
    "            if node.val in self.li:\n",
    "                self.li.remove(node.val)\n",
    "            else:\n",
    "                self.li.add(node.val)\n",
    "        func(root)\n",
    "        return self.num\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        s = set()\n",
    "        ans = 0\n",
    "        def dfs(root):\n",
    "            if root.val in s:\n",
    "                s.remove(root.val)\n",
    "            else:\n",
    "                s.add(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                if len(s) < 2:\n",
    "                    nonlocal ans\n",
    "                    ans += 1\n",
    "            else:\n",
    "                if root.left:\n",
    "                    dfs(root.left)\n",
    "                if root.right:\n",
    "                    dfs(root.right)\n",
    "            if root.val in s:\n",
    "                s.remove(root.val)\n",
    "            else:\n",
    "                s.add(root.val)\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        def tree(node,counter):\n",
    "\n",
    "            if not node:\n",
    "                return 0\n",
    "            counter[node.val]+=1\n",
    "            res = 0\n",
    "            if not node.left and not node.right:\n",
    "                if isPseudoPalindrome(counter):\n",
    "                    res = 1\n",
    "            else:\n",
    "                res = tree(node.left,counter)+tree(node.right,counter)\n",
    "            counter[node.val]-=1\n",
    "            return res\n",
    "\n",
    "        def isPseudoPalindrome(counter: list[int]) -> bool:\n",
    "            odd = 0\n",
    "            for value in counter:\n",
    "                if value % 2 == 1:\n",
    "                    odd += 1\n",
    "            return odd <= 1\n",
    "\n",
    "        counter = [0] * 10\n",
    "        return tree(root, counter)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root, cnt):\n",
    "            nonlocal ans\n",
    "            if not root.left and not root.right:\n",
    "                cnt ^= 1 << root.val\n",
    "                ans += 1 if cnt == (cnt & -cnt) else 0\n",
    "                return \n",
    "            if root.left:\n",
    "                dfs(root.left, cnt ^ (1 << root.val))\n",
    "            if root.right:\n",
    "                dfs(root.right, cnt ^ (1 << root.val))\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        def count_1(num):\n",
    "            # print(bin(num))\n",
    "            ans = 0\n",
    "            for i in range(1,10):\n",
    "                ans += num>>i & 1\n",
    "            # print(ans,int(ans<=1))\n",
    "            return int(ans<=1)\n",
    "        n = 0\n",
    "        def dfs(node,site):\n",
    "            nonlocal n\n",
    "            if not node.left and not node.right:\n",
    "                n += count_1(site ^ 1<<node.val)\n",
    "                \n",
    "                \n",
    "            if node.left:\n",
    "                dfs(node.left,site^1<<node.val)\n",
    "            if node.right:\n",
    "                dfs(node.right,site^1<<node.val)\n",
    "        dfs(root,0)\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        memo = [0] * 10\n",
    "        ans = 0\n",
    "        def dfs(node, depth):\n",
    "            memo[node.val] += 1\n",
    "            if not node.left and not node.right:\n",
    "                # 到叶子了\n",
    "                cnt = 0\n",
    "                for v in memo:\n",
    "                    if v % 2:\n",
    "                        cnt += 1\n",
    "                if depth % 2 and cnt == 1 or cnt == 0:\n",
    "                    nonlocal ans\n",
    "                    ans += 1\n",
    "            \n",
    "            if node.left:\n",
    "                dfs(node.left, depth + 1)\n",
    "            if node.right:\n",
    "                dfs(node.right, depth + 1)\n",
    "            memo[node.val] -= 1\n",
    "        dfs(root, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        val_count = [0] * 9\n",
    "        def check(node,now_deepth):\n",
    "            now_result = 0\n",
    "            now_deepth +=1\n",
    "            val_count[node.val-1] +=1\n",
    "            if node.left:\n",
    "                now_result += check(node.left,now_deepth)\n",
    "            if node.right:\n",
    "                now_result += check(node.right,now_deepth)\n",
    "            if not node.left and not node.right:\n",
    "                if now_deepth % 2 !=0:\n",
    "                    odd_count = 0\n",
    "                    for each in val_count:\n",
    "                        if each % 2 !=0:\n",
    "                            odd_count +=1\n",
    "                            if odd_count == 2:\n",
    "                                val_count[node.val-1]-=1\n",
    "                                return 0\n",
    "                    val_count[node.val-1]-=1\n",
    "                    return 1\n",
    "                else:\n",
    "                    for each in val_count:\n",
    "                        if each % 2 !=0:\n",
    "                            val_count[node.val-1]-=1\n",
    "                            return 0\n",
    "                    val_count[node.val-1]-=1\n",
    "                    return 1 \n",
    "            val_count[node.val-1]-=1\n",
    "            return now_result\n",
    "        return check(root,0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        all_f = 2 ** 9 - 1\n",
    "        res = [ 0 ]\n",
    "\n",
    "        def inner(node, is_terminal, seen):\n",
    "            if node != None:\n",
    "                f = (seen >> (node.val - 1)) % 2\n",
    "                if f == 0:\n",
    "                    next_seen = seen | (1 << (node.val - 1))\n",
    "                else:\n",
    "                    next_seen = seen & (all_f - (1 << (node.val - 1)))\n",
    "                \n",
    "                next_is_terminal = (node.left == None and node.right == None)\n",
    "                inner(node.left, next_is_terminal, next_seen)\n",
    "                inner(node.right, next_is_terminal, next_seen)\n",
    "            elif is_terminal:\n",
    "                c = 0\n",
    "                while seen > 0:\n",
    "                    f = seen % 2\n",
    "                    if f == 1:\n",
    "                        c += 1\n",
    "                    \n",
    "                    seen = seen >> 1\n",
    "                \n",
    "                if c <= 1:\n",
    "                    res[0] += 1\n",
    "                \n",
    "                \n",
    "        \n",
    "        inner(root, (root.left == None and root.right == None), 0)\n",
    "        return res[0] // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root,visited,cnt):\n",
    "            if not root.left and not root.right:\n",
    "                #print(f'到达叶节点路径经过{visited},cnt{cnt}')\n",
    "                g = 0\n",
    "                if cnt % 2 == 0:\n",
    "                    for key,value in dic.items():\n",
    "                        if value % 2 != 0:\n",
    "                            g += 1\n",
    "                    return int(g == 0)\n",
    "                else:\n",
    "                    for key,value in dic.items():\n",
    "                        if value % 2 != 0:\n",
    "                            g += 1\n",
    "                    return int(g <= 1)\n",
    "            res = 0\n",
    "            if root.left:\n",
    "                visited[root.left.val] += 1\n",
    "                res += dfs(root.left,visited,cnt+1)\n",
    "                visited[root.left.val] -= 1\n",
    "            if root.right:\n",
    "                visited[root.right.val] += 1\n",
    "                res += dfs(root.right,visited,cnt+1)\n",
    "                visited[root.right.val] -= 1\n",
    "            return res\n",
    "        dic = defaultdict(int)\n",
    "        dic[root.val] += 1\n",
    "        return dfs(root,dic,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        # path = [root.val]\n",
    "        path = Counter([root.val])\n",
    "        ans = []\n",
    "        def dfs(i):\n",
    "            if i.left is None and i.right is None:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            if i.left: path[i.left.val] += 1; dfs(i.left); path[i.left.val] -= 1\n",
    "            if i.right: path[i.right.val] += 1; dfs(i.right); path[i.right.val] -= 1\n",
    "        dfs(root)\n",
    "        # print(ans)\n",
    "        result = 0\n",
    "        for i in ans:\n",
    "            # 1 2 1    1  2 2 1\n",
    "            if sum(k for j,k in i.items()) % 2 and sum(k%2 for j,k in i.items()) <= 1 or all(k%2==0 for j,k in i.items()):\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int: \n",
    "        res = 0\n",
    "        def dfs(node, tmp):\n",
    "            nonlocal res\n",
    "            if not node.left and not node.right:\n",
    "                if len({k:v for k, v in tmp.items() if v % 2 != 0}) <= 1: \n",
    "                    res += 1\n",
    "                return  \n",
    "            else:\n",
    "                for n in (node.left, node.right):\n",
    "                    if n: \n",
    "                        tmp[n.val] += 1\n",
    "                        dfs(n, tmp)\n",
    "                        tmp[n.val] -= 1\n",
    "                return\n",
    "        tmp = collections.defaultdict(int)\n",
    "        tmp[root.val] += 1\n",
    "        dfs(root, tmp)\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        cnt = [0] * 10\n",
    "\n",
    "        def traverse(node:TreeNode, cnt:dict,res:int):\n",
    "            cnt[node.val] = (cnt[node.val] + 1) % 2\n",
    "            # print(node.val, cnt)\n",
    "            cnt_c = cnt.copy()\n",
    "            if node.left:\n",
    "                res = traverse(node.left, cnt, res)\n",
    "            if node.right:\n",
    "                res = traverse(node.right, cnt_c, res)\n",
    "\n",
    "            # 到达叶节点 且 回文\n",
    "            if node.left is None and node.right is None:\n",
    "                if sum(cnt) < 2:\n",
    "                    # print(cnt)\n",
    "                    res += 1\n",
    "\n",
    "            return res\n",
    "\n",
    "        return traverse(root,cnt,0)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        def check(root: Optional[TreeNode],countque:list[int])->int:\n",
    "            try:\n",
    "                index = countque.index(root.val)\n",
    "                countque.pop(index)\n",
    "            except:\n",
    "                countque.append(root.val)\n",
    "            # print(countque)\n",
    "            if root.left == None and root.right == None:\n",
    "                if len(countque) <= 1 :\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            countL ,countR = 0,0\n",
    "            if root.left != None:\n",
    "                countL = check(root.left,countque.copy())\n",
    "            if root.right != None:\n",
    "                countR = check(root.right,countque.copy())\n",
    "            return countL+ countR\n",
    "\n",
    "        return check(root,[])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        val_count:list = [True]*10\n",
    "        res = self.dfs(root,val_count)\n",
    "\n",
    "        return res\n",
    "\n",
    "    \n",
    "    def dfs(self, node: Optional[TreeNode], val_count: list ):\n",
    "        val_count[node.val]=not val_count[node.val]\n",
    "        # print(node.val)\n",
    "        # print(val_count)\n",
    "\n",
    "        if not any([node.left,node.right]):\n",
    "            false_count = val_count.count(False)\n",
    "            if false_count == 0 or false_count == 1:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        left_num=0\n",
    "        right_num=0\n",
    "\n",
    "        if node.left:\n",
    "            left_num += self.dfs(node.left,val_count.copy())\n",
    "        \n",
    "        if node.right:\n",
    "            right_num += self.dfs(node.right,val_count.copy())\n",
    "        \n",
    "        return left_num + right_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:\n",
    "        # 路径是伪回文：某个节点值出现次数为单数的最多只有一个\n",
    "        times = [0] * 10\n",
    "        res = 0\n",
    "        def dfs(node, curtimes):\n",
    "            nonlocal res\n",
    "            curtimes[node.val] += 1\n",
    "            if not node.left and not node.right:\n",
    "                if sum([i%2 for i in curtimes]) <= 1:\n",
    "                    res += 1\n",
    "                return\n",
    "            if node.left:\n",
    "                dfs(node.left, curtimes[:])\n",
    "            if node.right:\n",
    "                dfs(node.right, curtimes[:])\n",
    "        \n",
    "        dfs(root, times)\n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
